1. Field of the Invention
The invention relates generally to networking devices and more specifically to caching data contained in packet buffers.
2. Background Information
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The nodes typically communicate by exchanging discrete frames or packets of data according to pre-defined protocols, such as the Transmission Control Protocol/internet Protocol (TCP/IP) or the Internetwork Packet eXchange (IPX) protocol.
The topology of a computer network can vary greatly. For example, the topology may comprise a single LAN containing a single intermediate node of a type such as, e.g., a hub, with end-nodes attached to the hub. A more complex network may contain one or more local area networks interconnected through a complex intermediate internetwork comprising a plurality of other types of intermediate nodes, such as switches or routers, to form a WAN. Each of these latter intermediate nodes typically contain a central processor that enables the intermediate node to, inter alia, route or switch the packets of data along the interconnected links from, e.g., a source end-node that originates the data to a destination end-node that is designated to receive the data. Often, these intermediate nodes employ packet buffers to temporarily hold packets that are processed by the nodes.
Packet buffers often comprise one or more memory devices that are arranged to form one or more First-In First-Out (FIFO) queues where each queue is associated with a particular input or output line. The size of each FIFO queue often depends on the rate of the line associated with the queue, as well as the time it takes for a packet to be processed by the intermediate node. For example, assume an input line on an intermediate node has a line rate of 1 Gigabits per second (Gb/s) and a packet takes 250 milliseconds (ms) to be processed by the node. The FIFO queue size can be determined by multiplying the line rate times the processing rate, thus yielding a queue size of at least 250 megabits (Mb).
The line rates associated with the input or output lines typically define the minimum required memory bandwidth of the packet buffer needed to support those lines. Memory bandwidth is often determined by taking the reciprocal of the “random cycle time” (tRC) associated with the memory devices that comprise the packet buffer and multiplying this result by the number of bits that can be transferred to the memory devices at a time. For example, assume a packet buffer can handle 64-bit data transfers and the memory devices that comprise the buffer have a tRC of 50 nanoseconds (ns), the memory bandwidth for the packet buffer is 1.2 Gb/s.
A typical intermediate node may comprise many line cards where each line card contains many ports and each port comprises an input line and an output line. Moreover, each line may operate at a rate of 1 Gb/s or greater. Thus, packet buffers for intermediate nodes are often large and operate at a very-high memory bandwidth. For example, assume an intermediate node has four ports with two lines per port and each line operates at a rate of 1 Gb/s. Further assume the intermediate node can process a packet in 250 ms and that data is transferred to and from the packet buffer using 64-bit data transfers. The memory bandwidth for the packet buffer must be at least 8 Gb/s and the tRC for the memory devices must be 8 ns or less. Moreover, the size of each FIFO must be at least 250 Mb yielding an overall packet buffer size of 1 gigabit (Gb).
In order to meet the high-bandwidth requirements associated with high-speed data communication lines, conventional packet buffer design mandates use of solely high-speed memory devices, such as Static Random Access Memory (SRAM), because their bandwidth and tRC is often sufficient to meet the rigorous requirements demanded by high speed input/output lines. However, high-speed memory devices are often very costly and not sufficiently dense to make them practical to be used for such an implementation.
An alternative technique for implementing a high-speed high-density packet buffer has been described in S. Iyer et al., Analysis of a Memory Architecture for Fast Packet Buffers, IEEE Workshop on High Performance Switching and Routing, IEEE, May 2001, pp. 368-373. This technique employs a combination of high speed devices arranged as a head and tail cache and low-speed high-density devices, such as Dynamic Random Access Memory (DRAM), arranged to hold the FIFO queues. Moreover, the technique employs a memory management algorithm that utilizes a look-ahead arrangement to determine the order data is read from the low-speed devices to replenish the head cache. However, the technique does not scale well with respect to the number of FIFO queues and consequently may be inapplicable in systems that contain a large number of queues, e.g., greater than 512. It would be desirable to have a technique for implementing a high-speed high-density packet buffer that scales well to systems that employ a large number of queues.